#include "stdafx.h"
#include "CLongesCommonSubsequece.h"
#include "include/tool.h"
#include <boost/numeric/ublas/matrix.hpp>
#include <gtest/gtest.h>

using namespace boost::numeric::ublas;

template <typename T>
void LcsLength(const std::vector<T> &A, const std::vector<T> &B, matrix<int> &c, matrix<int> &b) {
    for (int i = 0; i <= A.size(); ++i) {
        c(i, 0) = 0;
    }
    for (int j = 0; j <= B.size(); ++j) {
        c(0, j) = 0;
    }
    for (int i = 0; i <= A.size(); ++i) {
        b(i, 0) = 0;
    }
    for (int i = 0; i <= B.size(); ++i) {
        b(0, i) = 0;
    }
    for (int i = 0; i <= A.size()-1; ++i) {
        for (int j = 0; j <= B.size()-1; ++j) {
            int ii = i+1, jj = j+1;
            if (A[i] == B[j]) {
                c(ii, jj) = c(ii-1, jj-1)+1;
                b(ii, jj) = 0;
            } else if (c(ii-1, jj) >= c(ii, jj-1)) {
                c(ii, jj) = c(ii-1, jj);
                b(ii, jj) = 1;
            } else {
                c(ii, jj) = c(ii, jj-1);
                b(ii, jj) = -1;
            }
        }
    }
}

template <typename T>
void LcsPrint(const matrix<int> &b, const std::vector<T> &A, int i, int j) {
    if (i == 0 || j == 0) {
        return;
    }
    if (b(i, j) == 0) {
        LcsPrint(b, A, i-1, j-1);
        std::cout << A[i-1] << " ";
    } else if (b(i, j) == 1) {
        LcsPrint(b, A, i-1, j);
    } else {
        LcsPrint(b, A, i, j-1);
    }
}

template <typename T>
void LcsPrint2(const std::vector<T> &A, const std::vector<T> &B, matrix<int> &c, int i, int j) {
    if (i == 0 || j == 0) {
        return;
    }
    if (A[i-1] == B[j-1]) {
        LcsPrint2(A, B, c, i-1, j-1);
        std::cout << A[i-1] << " ";
    } else if (c(i-1, j) >= c(i, j-1)) {
        LcsPrint2(A, B, c, i-1, j);
    } else {
        LcsPrint2(A, B, c, i, j-1);
    }
}


template <typename T>
int MemoizedLcsLengthLookup(const std::vector<T> &A, const std::vector<T> &B, matrix<int> &c, int i, int j) {
    if (c(i, j) < std::numeric_limits<int>::max()) {
        return c(i, j);
    }
    if ( i == 0 || j == 0) {
        c(i, j) = 0;
        return c(i, j);
    }
    if (A[i-1] == B[j-1]) {
        c(i, j) = MemoizedLcsLengthLookup(A, B, c, i-1, j-1)+1;
    } else {
        c(i, j) = std::max(MemoizedLcsLengthLookup(A, B, c, i-1, j), MemoizedLcsLengthLookup(A, B, c, i, j-1));
    }
    return c(i, j);
}

template <typename T>
int MemoizedLcsLength(const std::vector<T> &A, const std::vector<T> &B, matrix<int> &c) {
    for (int i = 0; i <= A.size(); ++i) {
        for (int j = 0; j <= B.size(); ++j) {
            c(i, j) = std::numeric_limits<int>::max();
        }
    }

    return MemoizedLcsLengthLookup(A, B, c, A.size(), B.size());
}

CLongesCommonSubsequece::CLongesCommonSubsequece()
{
    //ctor
}

CLongesCommonSubsequece::~CLongesCommonSubsequece()
{
    //dtor
}

int CLongesCommonSubsequece::run(void) {
    {
        std::cout << "the long common subsequece between A and B : 0 and 1 sequence" << std::endl;
        int A[] = {1, 0, 0, 1, 0, 1, 0, 1};
        int B[] = {0, 1, 0, 1, 1, 0, 1, 1, 0};

        std::vector<int> AA = create_from_array(A, SIZE(A));
        std::vector<int> BB = create_from_array(B, SIZE(B));
        std::cout << "A : ";
        print_vector(AA);
        std::cout << "B : ";
        print_vector(BB);

        matrix<int> c(AA.size()+1, BB.size()+1), b(AA.size()+1, BB.size()+1);
        LcsLength(AA, BB, c, b);
        std::cout << "matrix c : " << std::endl;
        print_matrix(c);
        std::cout << "matrix b : " << std::endl;
        print_matrix(b);
        LcsPrint(b, AA, int(AA.size()), int(BB.size()));
        std::cout << std::endl;
    }

    {
        std::cout << "the long common subsequece between A and B : string sequence" << std::endl;
        char A[] = {'A', 'B', 'C', 'B', 'D', 'A', 'B'};
        char B[] = {'B', 'D', 'C', 'A', 'B', 'A'};

        std::vector<char> AA = create_from_array(A, SIZE(A));
        std::vector<char> BB = create_from_array(B, SIZE(B));
        std::cout << "A : ";
        print_vector(AA);
        std::cout << "B : ";
        print_vector(BB);
        matrix<int> c(AA.size()+1, BB.size()+1), b(AA.size()+1, BB.size()+1);
        LcsLength(AA, BB, c, b);

        std::cout << "matrix c : " << std::endl;
        print_matrix(c);
        std::cout << "matrix b : " << std::endl;
        print_matrix(b);

        //LcsPrint(b, AA, int(AA.size()), int(BB.size()));
        LcsPrint2(AA, BB, c, int(AA.size()), int(BB.size()));
        std::cout << std::endl;
    }

    {
        std::cout << "the long common subsequece between A and B : string sequence" << std::endl;
        std::cout << "using memoized lookup." << std::endl;
        char A[] = {'A', 'B', 'C', 'B', 'D', 'A', 'B'};
        char B[] = {'B', 'D', 'C', 'A', 'B', 'A'};

        std::vector<char> AA = create_from_array(A, SIZE(A));
        std::vector<char> BB = create_from_array(B, SIZE(B));
        std::cout << "A : ";
        print_vector(AA);
        std::cout << "B : ";
        print_vector(BB);
        matrix<int> c(AA.size()+1, BB.size()+1);
        MemoizedLcsLength(AA, BB, c);

        std::cout << "matrix c : " << std::endl;
        print_matrix(c, 10);

        //LcsPrint(b, AA, int(AA.size()), int(BB.size()));
        LcsPrint2(AA, BB, c, int(AA.size()), int(BB.size()));
        std::cout << std::endl;
    }

    {
        std::cout << "find the increasing long common subsequece :" << std::endl;
        int A[] = {5, 3, 94, 46, 33, 778, 332, 56};
        int B[] = {3, 5, 33, 46, 56, 94, 332, 778};

        std::vector<int> AA = create_from_array(A, SIZE(A));
        std::vector<int> BB = create_from_array(B, SIZE(B));
        std::cout << "A : ";
        print_vector(AA);
        std::cout << "B : ";
        print_vector(BB);

        matrix<int> c(AA.size()+1, BB.size()+1), b(AA.size()+1, BB.size()+1);
        LcsLength(AA, BB, c, b);
        std::cout << "matrix c : " << std::endl;
        print_matrix(c);
        std::cout << "matrix b : " << std::endl;
        print_matrix(b);
        LcsPrint(b, AA, int(AA.size()), int(BB.size()));
        std::cout << std::endl;
    }

    return 0;
}

TEST(CLongesCommonSubsequece, run)
{
	CLongesCommonSubsequece().run();
}
